---
title: "深入 next、字符串处理(头疼）"
created: 2025-11-28
tags:
  - 算法
---

# 深入 next、字符串处理(头疼）

## 题目 [动物园](https://www.acwing.com/problem/content/description/1002/)

![[image-38c66d64.png]]

## 思路分析

气到了 学不来

看似简单 本来是因为求的是最长不公共前后缀长度 发现是数量

对这个cnt实在理解不了 模拟了半天 也还是不行

### 题目逻辑

1. **KMP算法的next数组**：KMP算法中的next数组用于记录字符串的每个位置之前的子串中，最长的相等的前缀和后缀的长度。例如，在字符串"abcababc"中，`next[5] = 2`意味着前5个字符"abcab"中，最长的相同前后缀是"ab"，长度为2。
2. **num数组的定义**：题目要求求出一个num数组，对于字符串S的前i个字符构成的子串，num[i]表示既是它的后缀同时又是它的前缀，并且这个后缀与这个前缀不重叠的字符串的数量。这是一个对KMP算法的扩展应用。
3. **求解方法**：通过修改KMP算法来实现。在计算next数组的同时，利用next数组来计算每个前缀的非重叠前后缀的数量。最后，将所有前缀的非重叠前后缀数量加一后的值相乘，并对1,000,000,007取模得到最终答案。

### 代码解析

代码中的关键步骤如下：

- **初始化**：对每个测试用例，首先读入字符串，并初始化`cnt[1] = 1`，因为第一个字符没有前后缀。
- **计算next数组和cnt数组**：通过一个循环计算next数组和cnt数组。对于字符串的每一个字符，如果当前字符与它前面的某个前缀的下一个字符相同，则更新next值。同时，利用next数组来更新cnt数组，`cnt[i] = cnt[ne[i]] + 1`，这里的+1表示包括当前字符本身作为一个长度为1的前后缀。
- **计算结果**：初始化一个变量`ans = 1`，遍历字符串的每一个位置，利用next数组和cnt数组计算每个位置的贡献，即`((LL)cnt[j] + 1) % M`，然后将这些值累乘得到最终结果。
- **输出结果**：对每个测试用例，输出计算得到的结果模1,000,000,007。

### 逻辑和实现的挑战

- **理解KMP算法**：需要深入理解KMP算法，尤其是next数组的计算方法和含义。
- **扩展应用**：在KMP算法的基础上进行扩展，引入num数组的概念，并计算所有前缀的非重叠前后缀数量的乘积。
- **精确处理边界条件**：精确处理字符串的每一个位置，尤其是在处理前缀和后缀不重叠的逻辑时。

核心

### cnt数组的求解

`cnt`数组的目的是为了记录对于字符串S的每一个前缀，满足既是它的后缀又是它的前缀，并且这个后缀与这个前缀不重叠的字符串的数量加一。这里加一是因为考虑到每个前缀本身至少有一个不重叠的前后缀（即它自身）。

1. **初始化**：对于字符串的第一个字符，它没有前后缀，所以`cnt[1]`初始化为1。
2. **计算过程**：从字符串的第二个字符开始计算每个位置的`cnt`值。这个计算依赖于`ne`数组，它记录了字符串每个位置之前的子串中，最长的相等的前缀和后缀的长度。在计算`cnt[i]`时，我们查看`ne[i]`的值，即当前位置i的最长相等前后缀的长度，并将`cnt[ne[i]] + 1`作为`cnt[i]`的值。

- **为什么是**`cnt[ne[i]] + 1`：这里的思路是，对于位置i的子串，其最长的相等前后缀已经由`ne[i]`给出，而`cnt[ne[i]]`记录了这个最长前后缀对应的不重叠前后缀的数量。因为我们在考虑位置i的子串时，除了这个最长的前后缀外，i本身可能代表一个新的不重叠前后缀的开始（特别是对于重复字符的情况），所以我们需要加1。

### ans的求解

最终答案`ans`是通过将所有`cnt`数组中的值（每个值都加1）相乘，再对1,000,000,007取模得到的。这里，加1是因为`cnt`数组中的值已经考虑了至少一个不重叠的前后缀（即本身），所以直接用于乘积计算。

1. **初始化**：`ans`初始化为1，这是乘积操作的标准初始化值。
2. **计算过程**：遍历字符串的每一个位置i。对于每个位置i，我们需要确定不重叠前后缀的数量。由于`cnt`数组已经记录了包含当前字符的不重叠前后缀数量加一的值，我们直接使用`cnt[j] + 1`（这里j是根据KMP算法调整的，以确保不考虑重叠的前后缀）。

- **重要的一步**：在乘以`cnt[j] + 1`之前，我们需要确保考虑的前后缀不会导致重叠。这通过检查`j * 2 > i`来实现。如果`j * 2 > i`，则说明当前的最长前后缀导致重叠，需要通过回溯`ne[j]`来找到一个不重叠的前后缀。

1. **乘积并取模**：对于每个位置i的`cnt[j] + 1`，将其乘入`ans`中，并在每步中对1,000,000,007取模，以避免整数溢出。
2. **输出结果**：遍历完成后，`ans`就是所有不重叠前后缀数量加一的乘积对1,000,000,007取模的结果。

## 代码实现

```cpp
#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10, M = 1e9 + 7;

int ne[N], cnt[N]; //cnt数组存储每个位置的不重叠前后缀数量加一

char sc[N];

int main() {

    int t;

    scanf("%d", &t);

    while (t--)

    {

        scanf("%s", sc + 1);

        int n = strlen(sc + 1);

        cnt[1] = 1; // 字符串的第一个字符没有前后缀，所以初始值为1（只有字符本身）

        for (int i = 2, j = 0; i <= n; i++)

        {

            while (j && sc[i] != sc[j + 1])

                j = ne[j];

            if (sc[i] == sc[j + 1])

                j++;

            ne[i] = j;

            /*

            对于每个位置i，cnt[i]的值是cnt[ne[i]]+1。

            这里，ne[i]表示前i个字符构成的子串的最长前后缀的长度，

            cnt[ne[i]]表示这个最长前后缀对应的不重叠前后缀的数量，

            加1是因为考虑到S[i]本身也可以是一个单独的不重叠前后缀。

            */

            cnt[i] = cnt[ne[i]] + 1;//加一是在加上它本身，因为它本身相等也是允许的

        }

        LL ans = 1; // 初始化结果为1

        for (int i = 1, j = 0; i <= n; i++) {

            while (j && sc[i] != sc[j + 1])

                j = ne[j];

            if (sc[i] == sc[j + 1])

                j++;

            /*

            对于字符串S的某个位置i，要确保一个前后缀不重叠，前后缀的长度必须小于等于i的一半，

            因为如果前后缀长度大于i的一半，那么前后缀必然重叠。

            换句话说，如果最长前后缀的长度j满足j * 2 > i，则说明前后缀重叠

            */

            while (j && (j * 2 > i))

                j = ne[j]; // 如果前后缀重叠，则回溯到上一个匹配位置

            // 计算最终答案，cnt[j]表示不重叠前后缀的数量，加1是考虑到字符串本身

            ans = ans * ((LL)cnt[j] + 1) % M;

        }

        cout << ans % M << endl; // 输出结果

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[拓展 循环结问题(头疼警告）|拓展 循环结问题(头疼警告）]] 🏠 [[00-刷题理模型]] ➡️ [[串相关模型|串相关模型]]